#include <cstdio>

bool check[ 242 ];
int match[ 242 ], hide[ 242 ][ 242 ], n;

bool dfs( int p )
{
    int t, i;
    for ( i = 0; i < n * 2; i++ )
    {
        if ( hide[ i ][ p ] && !check[ i ] )
        {
            check[ i ] = true;
            t = match[ i ];
            match[ i ] = p;
            if ( t == -1 || dfs( t ) )
                return true;
            match[ i ] = t;
        }
    }
    return false;
}

int main( )
{
    int m, t, i, j, a, b, count;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%d", &n, &m);
        for ( i = 0; i < n * 2; i++ )
        {
            match[ i ] = -1;
            for ( j = 0; j < n * 2; j++ )
                hide[ i ][ j ] = false;
        }
        for ( i = 0; i < m; i++ )
        {
            scanf("%d%d", &a, &b);
            hide[ a - 1 ][ b + n - 1 ] = true;
        }
        count = 0;
        for ( i = 0; i < n * 2; i++ )
        {
            for ( j = 0; j < n * 2; j++ )
                check[ j ] = false;
            if ( dfs( i ) )
                count++;
        }
        printf("%d\n", n - count);
    }
    return 0;
}

